from typing import List
import heapq

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        # 邻接表
        self.mp = [[] for _ in range(n)]
        for u, v, w in edges:
            self.mp[u].append((v, w))
        self.INF = float('inf')
        self.n = n

    def addEdge(self, edge: List[int]) -> None:
        self.mp[edge[0]].append((edge[1], edge[2]))

    def shortestPath(self, node1: int, node2: int) -> int:
        # 查找两点之间的最短路径
        # 节点i 的最短路径
        dis = [self.INF] * self.n
        q = []
        # （距离，节点）
        heapq.heappush(q, (0, node1))
        dis[node1] = 0
        while q:
            cnt, u = heapq.heappop(q)
            # 到达终点
            if u == node2:
                return cnt
            if cnt != dis[u]:
                continue
            for v, w in self.mp[u]:
                if dis[u] + w < dis[v]:
                    dis[v] = dis[u] + w
                    heapq.heappush(q, (dis[v], v))
        return -1  # 无法到达终点

# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)